package LeetCode;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:14
 */
public class interview40 {
    public static void main(String[] args) {
        int[] arr = {3,2};
        int[] result = getLeastNumbers(arr,2);
        for (int i:result){
            System.out.print(i+"\t");
        }
    }

    public static int[] getLeastNumbers(int[] arr, int k) {
        int[] sort = quickSort(arr,0,arr.length-1);
        int[] result = new int[k];
        for (int i = 0; i < k; i++){
            result[i] = sort[i];
        }
        return result;
    }

    public static int[] quickSort(int[] arr,int left,int right){
        //先选出中值
        int midIndex = (left+right)/2;
        int midIndexValue = arr[midIndex];
        int l = left;
        int r = right;
        int temp = 0;
        while (l < r){
            while (arr[l] < midIndexValue){
                l++;
            }
            while (arr[r] > midIndexValue){
                r--;
            }

            if (l >= r) {//说明左边已经有序，不需用在进行排序
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //灵魂
            if (arr[l] == midIndexValue) {
                r--;
            }

            if (arr[r] == midIndexValue) {
                l++;
            }

        }
        //进行递归
        if (l == r){//left = 0; r = 1时或无限递归
            l++;
            r--;
        }
        if (left < r){
            quickSort(arr,left,r);
        }
        if (l < right){
            quickSort(arr,l,right);
        }
        return arr;
    }

    public int[] getLeastNumbers2(int[] arr, int k) {
        if (k == 0 || arr.length == 0){
            return new int[0];
        }
        // 默认是小顶堆，实现大顶堆需要重写一下比较器
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) ->  o2 - o1);
        for (int num : arr) {
            if (queue.size() < k){
                queue.offer(num);
            }else if (num < queue.peek()){
                queue.poll();
                queue.offer(num);
            }
        }
        // 返回堆中的元素
        int[] res = new int[queue.size()];
        int idx = 0;
        while (!queue.isEmpty()){
            res[idx++] = queue.poll();
        }
        return res;
    }
}
